백준 알고리즘 BJ1759 암호 만들기 이 문제는 조건에 맞는 모든 암호를 출력하는 것이다. 사전식으로 출력해야 하므로 A~Z순으로 정렬해주고, 문자에 중복이 없으므로 조합을 재귀함수로 구현하여 길이가 맞을 때 출력하면 쉽게 해결할 수 있다.... 백준 알고리즘재귀함수조합백준 알고리즘 BJ1260 DFS와 BFS DFS 깊이우선탐색과 BFS 너비우선탐색을 알고 구현할 수 있는지를 묻는 문제다. 입력 받은 값으로 인접행렬을 만든 후에 BFS를 Queue로 구현하고, DFS를 재귀함수로 구현하면 된다.... 백준 알고리즘BFSDFSBFS BJ16236 아기 상어 NxN 사이즈의 맵과 그 안에 물고기들과 상어의 위치가 주어진다. 상어는 자신보다 작은 물고기만 먹을 수 있고, 상어는 먹은 물고기의 수에 따라 크기가 증가한다. 문제는 상어가 물고기를 먹을 수 있는 시간을 요구한다. 물고기들을 리스트에 담아 관리하고, BFS를 이용해 구현했다.... 백준 알고리즘BFSBFS BJ15686 치킨 배달 백준 알고리즘조합백준 알고리즘 BJ1753 최단경로 (다익스트라) 정석적인 다익스트라 알고리즘 문제이다. 다익스트라의 과정은 1. 출발 정점 설정 2. 출발 정점과 연결된 정점들까지의 최소거리 저장 3. 방문하지 않은 정점 중 가장 비용이 적은 정점 선택 4. 해당 정점을 방문처리하고, 그 정점을 거칠 경우, 최소거리 갱신 5. 3~4과정을 모두 방문처리될 때까지 반복 큐를 이용하여 조건이 맞을 때, 큐에 추가해주며 진행하면 된다.... 백준 알고리즘다익스트라다익스트라 BJ1463 1로 만들기 DP 또는 재귀함수를 이용해 해결할 수 있다. 이 문제에서는 재귀함수를 이용했을 때 실행시간이 더 짧았지만, 여러 테스트 케이스를 출력한다면 DP를 활용할 때는 단순히 배열에 접근해 값만 가져오면 되기 때문에 DP가 유리하다.... 재귀함수백준 알고리즘DPDP BJ17135 캐슬 디펜스 요구하는 조건을 구현할 수 있는 지를 확인하는 문제이다. 완전탐색을 이용해 확인하는 방식으로 해결했다. 세 궁수의 자리를 배치하기 위해 조합을 이용했고, attack() selectTarget() eraseMonster() moveDown() 와 같은 필요한 함수를 구현해 사용했다.... 백준 알고리즘조합구현구현 [Baekjoon] 7579. 앱 [G3] DP 배낭 문제를 생각해보면 된다. 일단 행은 앱들을 하나씩 넣는다. 열을 메모리로 할지 비용으로 할지 정해야한다. 일반적으로 메모리로 해야 테이블의 끝 값으로 값을 구할 수 있어서 좋다. 그렇지만 메모리의 값이 너무 커서 시간초과가 발생한다. 따라서 비용이 열, 메모리가 값이다. 비용을 열로 생각했을 때 문제점은 dp 테이블의 맨 끝 값이 답이 아니다. dp의 마지막 줄을 다 채우고 m보다... 백준 알고리즘백준 알고리즘 BJ1786 찾기 (KMP 알고리즘) KMP 알고리즘을 활용하는 문제다. 부분 일치 테이블과 두개의 포인터를 활용해 문자열 속에서 원하는 문자열을 찾는 효율적인 방법이다.... 백준 알고리즘KMP 알고리즘KMP 알고리즘 [Baekjoon] 9251. LCS [G5] LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 첫 번째 문자열을 순회하며 알파벳을 key로 인덱스 리스트를 값으로 하는 딕셔너리를 만든다. {A:[0, 2] C:[1] Y:[3] K:[4] P:[5]} 두 번째 문자열을 순서대로 순회하며 하나씩 딕셔너리에서 값을 확... 백준 알고리즘백준 알고리즘 [Baekjoon] 1167. 트리의 지름 [G3] 전에 풀었던 1967. 트리의 지름 문제와 거의 유사하다. 차이점은 입력으로 들어오는 것이 부모와 자식 관계가 아닌 정점 두 사이의 연결이다. 양방향으로 다 입력이 들어오니 입력을 다 받아준 후 visited로 확인하여 한쪽 방향으로만 진행할 수 있도록 해준다. 재귀함수를 돌면서 입력받은 정점의 visited 인덱스를 1로 바꾼다. 그리고 자식 노드를 검사할 때 visited이 0인 자식노드... 백준 알고리즘백준 알고리즘 [Baekjoon] 11725. 트리의 부모 찾기 [S2] 방향이 없는 그래프를 연결하는 2차원 배열을 만든다. 부모 노드의 배열을 초기화한다. BFS로 탐색한다. 먼저 트리의 루트노드인 1을 큐에 담는다. 1부터 꺼내어 확인하며 자식 노드들의 부모 노드 값을 1로 바꿔준다. 각각의 값들을 꺼내 각각 연결되어 있는 노드들의 부모 노드 값을 큐에서 꺼낸 값으로 넣어준다. 이미 확인한 값들은 다시 확인하지 않게 0보다 큰 값이 부모 노드에 들어있으면 c... 백준 알고리즘백준 알고리즘 [Baekjoon] 1967. 트리의 지름 [G4] 트리는 사이클이 없는 무방향 그래프이다. 모든 경로들 중에서 가장 긴 것을 트리의 지름이라고 한다. 문제에서 주어진 루트 노드는 1이다. 그림으로 어떻게 풀지 생각해본다. 후위 순회를 하며 자식노드부터 확인을 한다. 분기점에 도달하면 왼쪽에는 분기점에서 가장 긴 길이를 왼쪽에 적는다. 현재 분기점을 최상위 루트로 하는 트리 지름의 길이를 오른쪽에 적는다. 현재 노드가 분기점이 아니면 길이만 ... 백준 알고리즘백준 알고리즘 [Baekjoon] 2263. 트리의 순회 [G2] 인오더와 포스트오더가 주어졌을 때 인오더 포스트 오더의 1부터 확인한다. 1이 인오더에서 순서를 확인하면 7이다. 따라서 1의 왼쪽과, 인오더에서 1의 순서인 7번째 순서 왼쪽 값이 1의 자식 노드이다. 1의 자식 노드를 확인해보면 3과 2임을 알 수 있다. 포스트오더로 값을 확인하며 인오더는 카운팅 배열로 어디있는지 확인한다!! (배열의 인덱스 : 노드 번호, 배열의 값 : 인오더에서의 위... 백준 알고리즘백준 알고리즘 [Baekjoon] 11444. 피보나치 수 6 [G2] n이 1,000,000,000,000,000,000과 같이 주어졌으므로 점화식으로 더하면서 DP로 풀면 무조건 O(n) 이므로 무조건 시간초과가 발생한다. 피보나치 수를 해결할 수 있는 방법들을 찾아본다. 피사노 주기 피보나치는 정수로 나누면 주기가 나타난다. 피사노 주기는 1,000,000,007도 너무 커서 사용할 수 없다. 피사노 주기를 사용하기에는 모듈러 연산을 수행할 값이 너무 크다... 백준 알고리즘백준 알고리즘 [Baekjoon] 2206. 벽 부수고 이동하기 [G4] 최단경로이니 BFS로 구현한다. visited를 3차원으로 표시한다. 2차원의 위치에 [이동거리, 상태]를 넣어준다. 상태는 방문하지 않은 경우 : 2, 벽을 부수고 방문한 경우 : 1, 벽을 부수지 않고 방문한 경우 : 0이다. 이동거리는 최대 이동거리보다 크게 대략 n * m으로 초기화 한다. 상태는 방문하지 않았으므로 2로 초기화한다. 델타 탐색을 할 때 벽을 만나는 경우, 현재 부순 ... 백준 알고리즘백준 알고리즘 IF : 조건문 문제풀이(1) JS 기초문법 / 알고리즘 자료구조를 배워가면서 코딩테스트 공부한다는건 여전히 어렵게 느껴지지만 백준 알고리즘( )를 통해 유형별로 문제 풀이를 연습하면서 자신감을 키우고 있는 중이다🔥 🟡 두 수 비교하기 <문제> : 두 정수 A와 B가 주어졌을 때, A와 B를 비교하는 프로그램을 작성하시오. <입력> : 첫째 줄에 A와 B가 주어진다. : A와 B가 같은 경우에는 '=='를 출력한다. 두수... 백준 알고리즘jsif문if문 [Baekjoon] 14846. 직사각형과 쿼리 [G4] 서로 다른 정수의 개수를 구하는 문제!! 범위가 주어져 있는데 2차원이니 2차원 누적합으로 해결한다. 딕셔너리로 key에는 수를 값에는 개수를 넣어준다. 수의 범위가 1~10이라서 굳이 딕셔너리를 안 쓰고 카운팅 배열을 써도 된다! 누적합을 구한다. 기준점을 정해야하는데 (0, 0)을 기준점으로 삼는다.(그림 그릴 땐 (0, 0)으로 잡았는데 문제에 1부터 표현하여 padding을 더해 (1... 백준 알고리즘백준 알고리즘 [Baekjoon] 11404. 플로이드 [G4] 처음에 어떻게 해결해야할지 한참 생각했는데, BFS로 탐색하는 경우 중복되는 값이 너무 많아 해결할 방법이 떠오르지 않았다. 따라서 해답을 찾아보니 플로이드 워셜 알고리즘을 이용하는 문제이다. 플로이드 워셜 알고리즘에 대해 우선적으로 학습하였다. 모든 정점에서 최단경로를 구할 때 사용하는 알고리즘이다. 플로이드 워셜 알고리즘은 정점의 수가 적고, 간선의 수가 많을 때 활용한다. O(n^3)인... 백준 알고리즘백준 알고리즘 [Baekjoon] 11660. 구간 합 구하기 5 [S1] 이 문제의 설명에 앞서 개인적으로 x, y를 행과 열로 나타내느냐의 의미에 오랫동안 씨름했다.. 평소 행렬을 나타낼 때 row와 col을 i, j로 나타내면 i를 y에 j를 x에 각각 연결해서 문제를 풀었는데, 흔히 쓰는 방식이 row에 x, col에 y를 쓰는 것이었다. 이 문제에서 y, x로 주어지고 설명이 간단히 주어졌는데 관습과 다르게 풀었어서 다른 곳에서 틀렸나 한참 헤맸다.. 앞으... 백준 알고리즘백준 알고리즘 [Baekjoon] 14453. Hoof, Paper, Scissors (Silver) [S2] N이 100000이라 O(n^2)으로 해결하려고 하면 시간초과가 난다. 누적합을 사용하여 O(n)으로 해결한다. H가 바위, P가 보, S가 가위이다. H, P, S의 누적합을 인덱스 별로 각각 2차원 배열에 담는다. 누적합을 첫번째 인덱스부터 탐색한다. 주먹 가위 보 중 2개를 뽑는다. 중복 없는 순열 (H, P), (H, S), (P, H), (P, S), (S, H), (S, P) A와... 백준 알고리즘백준 알고리즘 [Baekjoon] 2015. 수들의 합 4 [G5] 누적합을 활용한다. 딕셔너리를 활용해 이전 값들을 저장해준다. 왜냐면 현재 값들과 이전 값의 차이를 활용해야 하기 때문이다. 카운팅 배열을 사용할 수도 있지만 합이 2,000,000,000을 넘으니 사용하기 어렵다. 그림으로 생각해보자. 예제 1번을 보면 Input 위 같이 Input이 주어졌다. 누적합으로 표현하면 다음과 같다. 처음 padding을 넣어준다. 부분합이 0인 걸 찾아야 한다... 백준 알고리즘백준 알고리즘 [Baekjoon] 1644. 소수의 연속합 [G3] N이하의 소수를 찾는다. 에라토스테네스의 체로 소수를 찾아준다. 소수를 찾을 때마다 소수의 배열에 담아준다. 소수가 순서대로 정렬되어 있으니 따로 정렬할 필요 없다. N이하의 소수를 배열에 담고, 투포인터로 찾아준다. s와 e를 시작점에서 같이 움직인다. 현재 합이 더 크면 e를 움직이고 그 위치에 있는 수를 더한다. 합이 작으면 s를 움직이고 움직이면서 왼쪽에 있는 수를 하나 뺀다. s가 ... 백준 알고리즘백준 알고리즘 [Baekjoon] 1300. K번째 수 [G2] N이 100000까지 주어진다. 그러면 배열을 만들어서 넣으려면 시간초과가 발생한다. 다른 방법을 생각해봐야 한다.. 예제의 입력을 보면, n = 3, k = 7 예제를 배열로 만들어보면 다음과 같다. 오름차순으로 정렬 7번째 수는 6이다. 배열의 규칙성을 보면 행이 바뀔 때마다 2를 곱한다. 그러면 다음 규칙을 알 수 있다. 첫 줄은 1 ~ n 두 번째 줄은 2 ~ 2n, 2간격 세 번째 ... 백준 알고리즘백준 알고리즘 [Baekjoon] 1520. 내리막 길 [G4] DP 탑다운 방식으로 풀었다. DFS 백트래킹을 활용했고, DP에 나왔던 값은 저장해서 사용한다. 시작부분을 넣고 재귀를 호출하면 계속 재귀를 타고 들어가 arr(-1, -1)인 맨 끝까지 재귀로 들어가 안쪽부터 구한다. 탑다운 방식으로 해결하면 코드가 깔끔하다. 구하면서 갈림길에서는 썼던 값을 사용하기 위해 DP를 활용하는 것이다. 4방향으로 탐색하면서 나아가야하니 델타 탐색을 활용하고, ... 백준 알고리즘백준 알고리즘 [Baekjoon] 14501. 퇴사 [S3] 재귀를 활용한 DFS로 해결하는데 조합을 활용한다. 상담을 고르는 것과 고르지 않는 것! 날짜만큼 진행시켜주니 백트래킹이라 할 수 있다. 재귀 호출할 때 상담의 날짜를 담아 호출하고, 날짜를 넘어가면 종료시킨다. 끝까지 갔을 때 최대 수익을 갱신한다. 하루에 상담일정이 하나씩 있으니 고르는 거와 안 고르는 걸로 조합으로 재귀 호출한다. 일정이 n에 도착하면 최댓값을 갱신하고 n을 넘어가면 상... 백준 알고리즘백준 알고리즘 [Baekjoon] 2110. 공유기 설치 [G5] 거리를 가능한 크게 설치하라는 문제이다. 문제만 봐도 매개변수탐색(이진탐색)을 사용할 수 있을 것 같다. 그럼 가능한지 예제로 확인해본다. Input 집의 좌표는 1, 2, 8, 4, 9이다. 좌표를 먼저 정렬한다. 1 2 4 8 9이다. 거리에 대한 매개변수를 표로 정리해보자! 거리 가능여부 다음과 같이 이진탐색을 활용하기 좋게 나타난다. 특정 거리로 공유기를 다 설치할 수 있는지 확인해서... 백준 알고리즘백준 알고리즘 [Baekjoon] 1005. ACM Craft [G3] 예제를 보며 어떤 형식으로 풀어야 할지 생각한다. Input 그림으로 그려보면 찾을 노드부터 역추적하면서 최대값을 찾는다. 같은 노드로 이어지는 경우 더 큰 값을 넣고 다음 간선을 탐색한다. python으로는 시간초과, pypy로는 메모리초과가 발생한다. 위 처럼 푸는 경우 문제점이 한 노드에 여러 노드를 거치는 횟수가 다른 간선들이 존재하면 필요 없이 중복 계산하는 경우가 발생한다. 위상정... 백준 알고리즘백준 알고리즘 [Baekjoon] 2589. 보물섬 [G5] 최단 거리를 구하는 문제로 BFS탐색을 활용한다. 모든 육지의 위치에서 BFS 탐색을 하며, BFS로 이동 거리가 가장 먼 거리를 출력한다. size로 같은 거리의 정점들을 순회하며 다음 거리의 정점들과 구별을 해준다. 순회가 끝나면 거리를 1씩 더한다. 그리고 다음 거리의 정점들을 다시 순회한다.... 백준 알고리즘백준 알고리즘 이전 기사 보기
BJ1759 암호 만들기 이 문제는 조건에 맞는 모든 암호를 출력하는 것이다. 사전식으로 출력해야 하므로 A~Z순으로 정렬해주고, 문자에 중복이 없으므로 조합을 재귀함수로 구현하여 길이가 맞을 때 출력하면 쉽게 해결할 수 있다.... 백준 알고리즘재귀함수조합백준 알고리즘 BJ1260 DFS와 BFS DFS 깊이우선탐색과 BFS 너비우선탐색을 알고 구현할 수 있는지를 묻는 문제다. 입력 받은 값으로 인접행렬을 만든 후에 BFS를 Queue로 구현하고, DFS를 재귀함수로 구현하면 된다.... 백준 알고리즘BFSDFSBFS BJ16236 아기 상어 NxN 사이즈의 맵과 그 안에 물고기들과 상어의 위치가 주어진다. 상어는 자신보다 작은 물고기만 먹을 수 있고, 상어는 먹은 물고기의 수에 따라 크기가 증가한다. 문제는 상어가 물고기를 먹을 수 있는 시간을 요구한다. 물고기들을 리스트에 담아 관리하고, BFS를 이용해 구현했다.... 백준 알고리즘BFSBFS BJ15686 치킨 배달 백준 알고리즘조합백준 알고리즘 BJ1753 최단경로 (다익스트라) 정석적인 다익스트라 알고리즘 문제이다. 다익스트라의 과정은 1. 출발 정점 설정 2. 출발 정점과 연결된 정점들까지의 최소거리 저장 3. 방문하지 않은 정점 중 가장 비용이 적은 정점 선택 4. 해당 정점을 방문처리하고, 그 정점을 거칠 경우, 최소거리 갱신 5. 3~4과정을 모두 방문처리될 때까지 반복 큐를 이용하여 조건이 맞을 때, 큐에 추가해주며 진행하면 된다.... 백준 알고리즘다익스트라다익스트라 BJ1463 1로 만들기 DP 또는 재귀함수를 이용해 해결할 수 있다. 이 문제에서는 재귀함수를 이용했을 때 실행시간이 더 짧았지만, 여러 테스트 케이스를 출력한다면 DP를 활용할 때는 단순히 배열에 접근해 값만 가져오면 되기 때문에 DP가 유리하다.... 재귀함수백준 알고리즘DPDP BJ17135 캐슬 디펜스 요구하는 조건을 구현할 수 있는 지를 확인하는 문제이다. 완전탐색을 이용해 확인하는 방식으로 해결했다. 세 궁수의 자리를 배치하기 위해 조합을 이용했고, attack() selectTarget() eraseMonster() moveDown() 와 같은 필요한 함수를 구현해 사용했다.... 백준 알고리즘조합구현구현 [Baekjoon] 7579. 앱 [G3] DP 배낭 문제를 생각해보면 된다. 일단 행은 앱들을 하나씩 넣는다. 열을 메모리로 할지 비용으로 할지 정해야한다. 일반적으로 메모리로 해야 테이블의 끝 값으로 값을 구할 수 있어서 좋다. 그렇지만 메모리의 값이 너무 커서 시간초과가 발생한다. 따라서 비용이 열, 메모리가 값이다. 비용을 열로 생각했을 때 문제점은 dp 테이블의 맨 끝 값이 답이 아니다. dp의 마지막 줄을 다 채우고 m보다... 백준 알고리즘백준 알고리즘 BJ1786 찾기 (KMP 알고리즘) KMP 알고리즘을 활용하는 문제다. 부분 일치 테이블과 두개의 포인터를 활용해 문자열 속에서 원하는 문자열을 찾는 효율적인 방법이다.... 백준 알고리즘KMP 알고리즘KMP 알고리즘 [Baekjoon] 9251. LCS [G5] LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 첫 번째 문자열을 순회하며 알파벳을 key로 인덱스 리스트를 값으로 하는 딕셔너리를 만든다. {A:[0, 2] C:[1] Y:[3] K:[4] P:[5]} 두 번째 문자열을 순서대로 순회하며 하나씩 딕셔너리에서 값을 확... 백준 알고리즘백준 알고리즘 [Baekjoon] 1167. 트리의 지름 [G3] 전에 풀었던 1967. 트리의 지름 문제와 거의 유사하다. 차이점은 입력으로 들어오는 것이 부모와 자식 관계가 아닌 정점 두 사이의 연결이다. 양방향으로 다 입력이 들어오니 입력을 다 받아준 후 visited로 확인하여 한쪽 방향으로만 진행할 수 있도록 해준다. 재귀함수를 돌면서 입력받은 정점의 visited 인덱스를 1로 바꾼다. 그리고 자식 노드를 검사할 때 visited이 0인 자식노드... 백준 알고리즘백준 알고리즘 [Baekjoon] 11725. 트리의 부모 찾기 [S2] 방향이 없는 그래프를 연결하는 2차원 배열을 만든다. 부모 노드의 배열을 초기화한다. BFS로 탐색한다. 먼저 트리의 루트노드인 1을 큐에 담는다. 1부터 꺼내어 확인하며 자식 노드들의 부모 노드 값을 1로 바꿔준다. 각각의 값들을 꺼내 각각 연결되어 있는 노드들의 부모 노드 값을 큐에서 꺼낸 값으로 넣어준다. 이미 확인한 값들은 다시 확인하지 않게 0보다 큰 값이 부모 노드에 들어있으면 c... 백준 알고리즘백준 알고리즘 [Baekjoon] 1967. 트리의 지름 [G4] 트리는 사이클이 없는 무방향 그래프이다. 모든 경로들 중에서 가장 긴 것을 트리의 지름이라고 한다. 문제에서 주어진 루트 노드는 1이다. 그림으로 어떻게 풀지 생각해본다. 후위 순회를 하며 자식노드부터 확인을 한다. 분기점에 도달하면 왼쪽에는 분기점에서 가장 긴 길이를 왼쪽에 적는다. 현재 분기점을 최상위 루트로 하는 트리 지름의 길이를 오른쪽에 적는다. 현재 노드가 분기점이 아니면 길이만 ... 백준 알고리즘백준 알고리즘 [Baekjoon] 2263. 트리의 순회 [G2] 인오더와 포스트오더가 주어졌을 때 인오더 포스트 오더의 1부터 확인한다. 1이 인오더에서 순서를 확인하면 7이다. 따라서 1의 왼쪽과, 인오더에서 1의 순서인 7번째 순서 왼쪽 값이 1의 자식 노드이다. 1의 자식 노드를 확인해보면 3과 2임을 알 수 있다. 포스트오더로 값을 확인하며 인오더는 카운팅 배열로 어디있는지 확인한다!! (배열의 인덱스 : 노드 번호, 배열의 값 : 인오더에서의 위... 백준 알고리즘백준 알고리즘 [Baekjoon] 11444. 피보나치 수 6 [G2] n이 1,000,000,000,000,000,000과 같이 주어졌으므로 점화식으로 더하면서 DP로 풀면 무조건 O(n) 이므로 무조건 시간초과가 발생한다. 피보나치 수를 해결할 수 있는 방법들을 찾아본다. 피사노 주기 피보나치는 정수로 나누면 주기가 나타난다. 피사노 주기는 1,000,000,007도 너무 커서 사용할 수 없다. 피사노 주기를 사용하기에는 모듈러 연산을 수행할 값이 너무 크다... 백준 알고리즘백준 알고리즘 [Baekjoon] 2206. 벽 부수고 이동하기 [G4] 최단경로이니 BFS로 구현한다. visited를 3차원으로 표시한다. 2차원의 위치에 [이동거리, 상태]를 넣어준다. 상태는 방문하지 않은 경우 : 2, 벽을 부수고 방문한 경우 : 1, 벽을 부수지 않고 방문한 경우 : 0이다. 이동거리는 최대 이동거리보다 크게 대략 n * m으로 초기화 한다. 상태는 방문하지 않았으므로 2로 초기화한다. 델타 탐색을 할 때 벽을 만나는 경우, 현재 부순 ... 백준 알고리즘백준 알고리즘 IF : 조건문 문제풀이(1) JS 기초문법 / 알고리즘 자료구조를 배워가면서 코딩테스트 공부한다는건 여전히 어렵게 느껴지지만 백준 알고리즘( )를 통해 유형별로 문제 풀이를 연습하면서 자신감을 키우고 있는 중이다🔥 🟡 두 수 비교하기 <문제> : 두 정수 A와 B가 주어졌을 때, A와 B를 비교하는 프로그램을 작성하시오. <입력> : 첫째 줄에 A와 B가 주어진다. : A와 B가 같은 경우에는 '=='를 출력한다. 두수... 백준 알고리즘jsif문if문 [Baekjoon] 14846. 직사각형과 쿼리 [G4] 서로 다른 정수의 개수를 구하는 문제!! 범위가 주어져 있는데 2차원이니 2차원 누적합으로 해결한다. 딕셔너리로 key에는 수를 값에는 개수를 넣어준다. 수의 범위가 1~10이라서 굳이 딕셔너리를 안 쓰고 카운팅 배열을 써도 된다! 누적합을 구한다. 기준점을 정해야하는데 (0, 0)을 기준점으로 삼는다.(그림 그릴 땐 (0, 0)으로 잡았는데 문제에 1부터 표현하여 padding을 더해 (1... 백준 알고리즘백준 알고리즘 [Baekjoon] 11404. 플로이드 [G4] 처음에 어떻게 해결해야할지 한참 생각했는데, BFS로 탐색하는 경우 중복되는 값이 너무 많아 해결할 방법이 떠오르지 않았다. 따라서 해답을 찾아보니 플로이드 워셜 알고리즘을 이용하는 문제이다. 플로이드 워셜 알고리즘에 대해 우선적으로 학습하였다. 모든 정점에서 최단경로를 구할 때 사용하는 알고리즘이다. 플로이드 워셜 알고리즘은 정점의 수가 적고, 간선의 수가 많을 때 활용한다. O(n^3)인... 백준 알고리즘백준 알고리즘 [Baekjoon] 11660. 구간 합 구하기 5 [S1] 이 문제의 설명에 앞서 개인적으로 x, y를 행과 열로 나타내느냐의 의미에 오랫동안 씨름했다.. 평소 행렬을 나타낼 때 row와 col을 i, j로 나타내면 i를 y에 j를 x에 각각 연결해서 문제를 풀었는데, 흔히 쓰는 방식이 row에 x, col에 y를 쓰는 것이었다. 이 문제에서 y, x로 주어지고 설명이 간단히 주어졌는데 관습과 다르게 풀었어서 다른 곳에서 틀렸나 한참 헤맸다.. 앞으... 백준 알고리즘백준 알고리즘 [Baekjoon] 14453. Hoof, Paper, Scissors (Silver) [S2] N이 100000이라 O(n^2)으로 해결하려고 하면 시간초과가 난다. 누적합을 사용하여 O(n)으로 해결한다. H가 바위, P가 보, S가 가위이다. H, P, S의 누적합을 인덱스 별로 각각 2차원 배열에 담는다. 누적합을 첫번째 인덱스부터 탐색한다. 주먹 가위 보 중 2개를 뽑는다. 중복 없는 순열 (H, P), (H, S), (P, H), (P, S), (S, H), (S, P) A와... 백준 알고리즘백준 알고리즘 [Baekjoon] 2015. 수들의 합 4 [G5] 누적합을 활용한다. 딕셔너리를 활용해 이전 값들을 저장해준다. 왜냐면 현재 값들과 이전 값의 차이를 활용해야 하기 때문이다. 카운팅 배열을 사용할 수도 있지만 합이 2,000,000,000을 넘으니 사용하기 어렵다. 그림으로 생각해보자. 예제 1번을 보면 Input 위 같이 Input이 주어졌다. 누적합으로 표현하면 다음과 같다. 처음 padding을 넣어준다. 부분합이 0인 걸 찾아야 한다... 백준 알고리즘백준 알고리즘 [Baekjoon] 1644. 소수의 연속합 [G3] N이하의 소수를 찾는다. 에라토스테네스의 체로 소수를 찾아준다. 소수를 찾을 때마다 소수의 배열에 담아준다. 소수가 순서대로 정렬되어 있으니 따로 정렬할 필요 없다. N이하의 소수를 배열에 담고, 투포인터로 찾아준다. s와 e를 시작점에서 같이 움직인다. 현재 합이 더 크면 e를 움직이고 그 위치에 있는 수를 더한다. 합이 작으면 s를 움직이고 움직이면서 왼쪽에 있는 수를 하나 뺀다. s가 ... 백준 알고리즘백준 알고리즘 [Baekjoon] 1300. K번째 수 [G2] N이 100000까지 주어진다. 그러면 배열을 만들어서 넣으려면 시간초과가 발생한다. 다른 방법을 생각해봐야 한다.. 예제의 입력을 보면, n = 3, k = 7 예제를 배열로 만들어보면 다음과 같다. 오름차순으로 정렬 7번째 수는 6이다. 배열의 규칙성을 보면 행이 바뀔 때마다 2를 곱한다. 그러면 다음 규칙을 알 수 있다. 첫 줄은 1 ~ n 두 번째 줄은 2 ~ 2n, 2간격 세 번째 ... 백준 알고리즘백준 알고리즘 [Baekjoon] 1520. 내리막 길 [G4] DP 탑다운 방식으로 풀었다. DFS 백트래킹을 활용했고, DP에 나왔던 값은 저장해서 사용한다. 시작부분을 넣고 재귀를 호출하면 계속 재귀를 타고 들어가 arr(-1, -1)인 맨 끝까지 재귀로 들어가 안쪽부터 구한다. 탑다운 방식으로 해결하면 코드가 깔끔하다. 구하면서 갈림길에서는 썼던 값을 사용하기 위해 DP를 활용하는 것이다. 4방향으로 탐색하면서 나아가야하니 델타 탐색을 활용하고, ... 백준 알고리즘백준 알고리즘 [Baekjoon] 14501. 퇴사 [S3] 재귀를 활용한 DFS로 해결하는데 조합을 활용한다. 상담을 고르는 것과 고르지 않는 것! 날짜만큼 진행시켜주니 백트래킹이라 할 수 있다. 재귀 호출할 때 상담의 날짜를 담아 호출하고, 날짜를 넘어가면 종료시킨다. 끝까지 갔을 때 최대 수익을 갱신한다. 하루에 상담일정이 하나씩 있으니 고르는 거와 안 고르는 걸로 조합으로 재귀 호출한다. 일정이 n에 도착하면 최댓값을 갱신하고 n을 넘어가면 상... 백준 알고리즘백준 알고리즘 [Baekjoon] 2110. 공유기 설치 [G5] 거리를 가능한 크게 설치하라는 문제이다. 문제만 봐도 매개변수탐색(이진탐색)을 사용할 수 있을 것 같다. 그럼 가능한지 예제로 확인해본다. Input 집의 좌표는 1, 2, 8, 4, 9이다. 좌표를 먼저 정렬한다. 1 2 4 8 9이다. 거리에 대한 매개변수를 표로 정리해보자! 거리 가능여부 다음과 같이 이진탐색을 활용하기 좋게 나타난다. 특정 거리로 공유기를 다 설치할 수 있는지 확인해서... 백준 알고리즘백준 알고리즘 [Baekjoon] 1005. ACM Craft [G3] 예제를 보며 어떤 형식으로 풀어야 할지 생각한다. Input 그림으로 그려보면 찾을 노드부터 역추적하면서 최대값을 찾는다. 같은 노드로 이어지는 경우 더 큰 값을 넣고 다음 간선을 탐색한다. python으로는 시간초과, pypy로는 메모리초과가 발생한다. 위 처럼 푸는 경우 문제점이 한 노드에 여러 노드를 거치는 횟수가 다른 간선들이 존재하면 필요 없이 중복 계산하는 경우가 발생한다. 위상정... 백준 알고리즘백준 알고리즘 [Baekjoon] 2589. 보물섬 [G5] 최단 거리를 구하는 문제로 BFS탐색을 활용한다. 모든 육지의 위치에서 BFS 탐색을 하며, BFS로 이동 거리가 가장 먼 거리를 출력한다. size로 같은 거리의 정점들을 순회하며 다음 거리의 정점들과 구별을 해준다. 순회가 끝나면 거리를 1씩 더한다. 그리고 다음 거리의 정점들을 다시 순회한다.... 백준 알고리즘백준 알고리즘 이전 기사 보기